package com.chj.zhongji.class03.test;

import java.util.Comparator;

public class Code06_TrappingRainWaterII {

	public static class Node {
		public int value;
		public int row;
		public int col;

		public Node(int v, int r, int c) {
			value = v;
			row = r;
			col = c;
		}

		@Override
		public String toString() {
			return "Node [value=" + value + ", row=" + row + ", col=" + col + "]";
		}
	}

	// MinHeap
	public static class NodeComparator implements Comparator<Node> {
		@Override
		public int compare(Node o1, Node o2) {
//			return o1.value - o2.value;
			return o2.value - o1.value;
		}
	}

	public static int trapRainWater(int[][] heightMap) {
		if (heightMap == null || heightMap.length == 0 || heightMap[0] == null || heightMap[0].length == 0) {
			return 0;
		}
		int N = heightMap.length;
		int M = heightMap[0].length;
		boolean[][] isEnter = new boolean[N][M];
		PriorityQueue<Node> heap = new PriorityQueue<>(new NodeComparator());
		for (int col = 0; col < M - 1; col++) {
			isEnter[0][col] = true;
			heap.enQueue(new Node(heightMap[0][col], 0, col));
		}
//		System.out.println("----enQueue--111---");
//		while (!heap.isEmpty()) {
//			System.out.println(heap.deQueue());
//		}
//		System.out.println("---------");
		for (int row = 0; row < N - 1; row++) {
			isEnter[row][M - 1] = true;
			heap.enQueue(new Node(heightMap[row][M - 1], row, M - 1));
		}
//		System.out.println("----enQueue--222---");
//		while (!heap.isEmpty()) {
//			System.out.println(heap.deQueue());
//		}
//		System.out.println("---------");

		for (int col = M - 1; col > 0; col--) {
			isEnter[N - 1][col] = true;
			heap.enQueue(new Node(heightMap[N - 1][col], N - 1, col));
		}

//		System.out.println("----enQueue--333---");
//		while (!heap.isEmpty()) {
//			System.out.println(heap.deQueue());
//		}
//		System.out.println("---------");
		for (int row = N - 1; row > 0; row--) {
			isEnter[row][0] = true;
			heap.enQueue(new Node(heightMap[row][0], row, 0));
		}
//		System.out.println("----enQueue--444---");
//		while (!heap.isEmpty()) {
//			System.out.println(heap.deQueue());
//		}
//		System.out.println("---------");
		int water = 0;
		int max = 0;
		int ii = 0;
		int jj = 0;
		while (!heap.isEmpty()) {
			Node cur = heap.deQueue();
			max = Math.max(max, cur.value);
			int r = cur.row;
			int c = cur.col;
			int value = 0;

			System.out.println((++ii) + "----enQueue--val---" + max);
			System.out.println(cur.value);
			System.out.println((++jj) + "----enQueue--val---");
			if (r > 0 && !isEnter[r - 1][c]) {
				value = heightMap[r - 1][c];
				water += Math.max(0, max - value);
				isEnter[r - 1][c] = true;
				System.out.println("r>0: " + value);
				heap.enQueue(new Node(heightMap[r - 1][c], r - 1, c));
			}

			if (r < N - 1 && !isEnter[r + 1][c]) {
				value = heightMap[r + 1][c];
				water += Math.max(0, max - value);
				isEnter[r + 1][c] = true;
				System.out.println("r>N-1: " + value);
				heap.enQueue(new Node(heightMap[r + 1][c], r + 1, c));

			}

//			System.out.println("----enQueue--555---");
//			while (!heap.isEmpty()) {
//				System.out.println(heap.deQueue());
//			}
//			System.out.println("---------");

			if (c > 0 && !isEnter[r][c - 1]) {
				value = heightMap[r][c - 1];
				water += Math.max(0, max - value);
				isEnter[r][c - 1] = true;
				System.out.println("c>0: " + value);
				heap.enQueue(new Node(heightMap[r][c - 1], r, c - 1));
			}
			if (c < M - 1 && !isEnter[r][c + 1]) {
				value = heightMap[r][c + 1];
				water += Math.max(0, max - value);
				isEnter[r][c + 1] = true;
				System.out.println("c < M - 1: " + value);
				heap.enQueue(new Node(heightMap[r][c + 1], r, c + 1));
			}
		}
		return water;
	}

	// MinHeap
	public static class MyComparator implements Comparator<Integer> {
		@Override
		public int compare(Integer o1, Integer o2) {
//			return o1 - o2;
			return o2 - o1;
		}
	}

	public static void main(String[] args) {
		int[][] matrix = new int[][] { { 100, 144, 221, 39, 47, 53, 66 }, // 0
				{ 100, 12, 13, 15, 16, 17, 180 }, // 1
				{ 230, 24, 25, 26, 27, 28, 290 }, // 2
				{ 440, 45, 46, 47, 48, 49, 500 }, // 3
				{ 650, 66, 67, 68, 69, 70, 710 }, // 4
				{ 96, 97, 98, 99, 100, 111, 122 }, // 5
				{ 166, 176, 186, 187, 190, 195, 200 }, // 6
				{ 233, 243, 321, 341, 356, 370, 380 } // 7
		};

		System.out.println(trapRainWater(matrix));
		System.out.println((4 << 1));
		System.out.println((4 >> 1));

		Integer[] data = { 88, 44, 53, 41, 16, 6, 70, 18, 85, 98, 81, 23, 36, 43, 37 };
//		BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
//			public int compare(Integer o1, Integer o2) {
////				return o2 - o1;
//				return o1 - o2;
//			}
//		});

		BinaryHeap<Integer> heap = new BinaryHeap<>(data, new MyComparator());
		System.out.println("----enQueue--444---");
		while (!heap.isEmpty()) {
			System.out.println(heap.remove());
		}
		System.out.println("---------");
	}
}
